1. Field of the Invention
This invention relates to digital signal processing and more particularly it relates to a device capable of performing specific arithmetic and logic functions required to perform various types of waveform signal processing tasks including transforms known collectively as fast Fourier transforms (FFT).
Fast Fourier transforms are a class of processes which are capable of performing Fourier transformation of signals with considerably fewer multiplication operations than normally is required for Fourier transformation. For example, direct evaluation of a discrete Fourier transform on N number of points requires N.sup.2 complex multiplications and additions. A fast Fourier transform requires only (N/2) log.sub.2 N number of computations. For an N=1024 points, this represents a computational savings of ninety-nine percent.
The fast Fourier transform is characterized by a large number of repetitive sequential operations of complex (real and imaginary) numbers in short loops. It is desirable to perform such computations as rapidly as possible to accommodate a broad spectrum of frequencies in real time applications where manipulation of the information in the transform domain is particularly convenient.
2. Description of the Prior Art
In the past, general purpose computers and bit slice machines have been adapted for waveform signal processing applications. General purpose computers, however, are generally expensive and have many unnecessary or limited functions when used in signal processing applications, specifically signal processing applications which approach real time speeds. The number of multiplications, data transfers, and the like, which must be performed during each sample period is extremely large, and the processing time is generally limited by the critical path of the central processing unit. For example, a typical bit slice-type central processing unit is the Am2903 Arithmetic Processor manufactured by Advanced Micro Devices, Inc. of Sunnyvale, Cal. The central element, the AM2903, contains an arithmetic logic unit and a 16-word scratch-pad memory with special multiply functions. However, the Am203 has a critical path which only permits the efficient implementation of a microprogrammed multiplication in a multi-cycle operation. It is therefore necessarily slower than a device capable of parallel hardware multiplication. Still further, the architecture of the Am2903 has only one arithmetic logic unit and one data bus. Thus a critical path time restraint exists if it is necesary to manipulate complex numbers, since two cycles are required for each such operation. Still further, the A2903 does not easily permit simultaneous memory access and arithmetic operation, thus establishing another critical path.
What is needed is a device capable of a high degree of parallel processing. Indeed, it is only by performing many operations in parallel that really high processing throughput may be achieved. The input/output structure of existing devices, including the Am2903 simply do not provide for the necessary interconnection, or flexibility of interconnection, between computational elements, storage elements and external devices to minimize critical path.